package data_structur.LinkList;

/**
 * 链表特点：1.链表以节点的形式存储
 *          2.节点包含data、next
 *          3.节点不一定在内存中连续存放
 *          4.链表不一定有头节点，需根据实际情况决定
 */
public class LinkListDemo {

    public static void main(String[] args) {
        // 测试
        HeroLinkList heroLinkList = new HeroLinkList();
        heroLinkList.list(heroLinkList.getHead());
        System.out.println("---倒着打印---");
        heroLinkList.printReverseHeroNode(heroLinkList.getHead(), 0);
        System.out.println("-------");
        System.out.println(heroLinkList.getLength(heroLinkList.getHead()));
        System.out.println(heroLinkList.update(new HeroNode(1, "阿哲", "芜湖翘皮嫩男")));
        heroLinkList.add(new HeroNode(2, "宋江", "及时雨"));
        System.out.println(heroLinkList.update(new HeroNode(1, "阿哲", "芜湖翘皮嫩男")));
        heroLinkList.add(new HeroNode(1, "朱哲宇", "芜湖型男"));
        heroLinkList.add(new HeroNode(1, "朱泽宇", "珠海型男"));
        heroLinkList.add(new HeroNode(5, "武松", "行者"));
        heroLinkList.add(new HeroNode(4, "关胜", "大刀"));
        heroLinkList.add(new HeroNode(3, "吴用", "智多星"));
        heroLinkList.add(new HeroNode(3, "酉用", "痣多星"));
        heroLinkList.list(heroLinkList.getHead());
        System.out.println("---倒着打印---");
        heroLinkList.printReverseHeroNode(heroLinkList.getHead(), 0);
        System.out.println("-------");
        System.out.println(heroLinkList.getLength(heroLinkList.getHead()));
        System.out.println("---反转---");
        HeroNode reversed = heroLinkList.reverseHeroNode(heroLinkList.getHead());
        heroLinkList.list(reversed);
        System.out.println("----------");
        System.out.println(heroLinkList.update(new HeroNode(1, "阿哲", "芜湖翘皮嫩男")));
        heroLinkList.list(heroLinkList.getHead());
        System.out.println("找倒数第2个： " + heroLinkList.findLastIndexNode(heroLinkList.getHead(), 2));
        System.out.println(heroLinkList.delete(3));
        heroLinkList.list(heroLinkList.getHead());
        System.out.println(heroLinkList.getLength(heroLinkList.getHead()));

    }

}

/**
 * 管理英雄
 */
class HeroLinkList {
    // 创建头节点
    private final HeroNode head = new HeroNode(0, "", "");

    /*
     基本操作
     */

    // 找到尾节点
    public HeroNode findTail(){
        HeroNode temp = head;
        while ( temp.next != null ){
            temp = temp.next;
        }
        return temp;
    }

    // 当考虑编号大小，且编号不能重复，需要寻找合适的位置，提供前一个节点
    public HeroNode findFrontNode(HeroNode heroNode){
        HeroNode temp = head;
        while (true){
            if (temp.next == null){
                break;
            } else if (heroNode.num < temp.next.num ){
                break;
            } else if (heroNode.num == temp.next.num){
                return null;
            } else {
                temp = temp.next;
            }
        }
        return temp;
    }

    // 新增英雄
    public String add(HeroNode heroNode){
        HeroNode frontNode = findFrontNode(heroNode);
        if (frontNode == null){
            System.out.println(heroNode.name + " --- Add Failed.");
            return heroNode.toString() + " --- Add Failed.";
        }
        if (frontNode.next != null){
            heroNode.next = frontNode.next;
        }
        frontNode.next = heroNode;
        return heroNode.toString() + " --- Add Success.";
    }

    // 遍历列表
    public void list(HeroNode head){
        if (head.next == null){
            System.out.println("LinkList is Empty, Fail to Show List.");
        } else {
            HeroNode temp = head.next;
            while (temp != null){
                System.out.println(temp);
                temp = temp.next;
            }
        }
    }


    // 根据编号更新英雄
    public String update(HeroNode heroNode){
        HeroNode temp = head;
        boolean found = false;
        if (temp.next == null){
            return "LinkList is Empty, Update Failed.";
        }
        while (true){
            if (temp.next == null ){
                return "No Such num, Update Failed.";
            } else if (temp.next.num == heroNode.num){
                found = true;
            }
            if (found){
                temp.next.name = heroNode.name;
                temp.next.nickName = heroNode.nickName;
                return "Update Success. " + heroNode;
            } else {
                temp = temp.next;
            }
        }
    }

    // 根据编号删除英雄
    public String delete(int num){
        HeroNode temp = head;
        boolean found = false;
        if (temp.next == null){
            return "LinkList is Empty, Delete Failed.";
        }
        while (true){
            if (temp.next == null ){
                return "No Such num, Delete Failed.";
            } else if (temp.next.num == num){
                found = true;
            }
            if (found){
                if (temp.next.next == null){
                    temp.next = null;
                } else {
                    temp.next = temp.next.next;
                }
                return "Delete Success.";
            } else {
                temp = temp.next;
            }
        }
    }


    /*
    面试题
     */

    // 一、获取单链表节点个数（如果带头结点，不需要将头结点计入）
    public int getLength(HeroNode head){
        int length = 0;
        if (head.next == null){
            return length;
        }
        HeroNode cur = head.next;
        while (cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    public HeroNode getHead(){
        return this.head;
    }

    // 二、查找单链表倒数第k个节点（新浪）
    // 思路：1、两次遍历，第一次获取单链表size，然后size-k得到节点的index，第二次遍历找到index并返回
    // 2、快慢指针，快指针找，返回慢指针
    public HeroNode findLastIndexNode(HeroNode head, int k){
        if(head.next == null){
            return null;
        }
        int size = getLength(head);
        if (k <= 0 || k > size){
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < size - k; i++) {
            cur = cur.next;
        }
        return cur;
    }

    // 三、反转单链表（腾讯）
    // 思路：头插法。
    // 新建一个新的反转后的reversedHead，从原本的link里遍历去，然后以此头插到reversedHead，
    // 注意：取出的第一个node也就是num为1的，是新link的尾结点，所以其next需设为null
    public HeroNode reverseHeroNode(HeroNode head){
        HeroNode reversedHead = new HeroNode(0, "", "");
        if (head.next == null || head.next.next == null) {
            return reversedHead;
        }
        HeroNode cur = head.next;
        while (cur != null){
            HeroNode nextOfCur = cur.next;
            if (reversedHead.next == null){
                cur.next = null;
                reversedHead.next = cur;
            } else {
                HeroNode temp = reversedHead.next;
                reversedHead.next = cur;
                cur.next = temp;
            }
            cur = nextOfCur;
        }
        return reversedHead;
    }

    // 四、从尾到头打印单链表(百度）
    // 鄙人思路：递归nb
    public void printReverseHeroNode(HeroNode head, int f){
        HeroNode cur = head.next;
        if (cur != null){
            printReverseHeroNode(cur, f + 1);
            System.out.println(cur);
        } else if (f == 0){
            System.out.println("LinkList is Empty, Fail to printReverseHeroNode.");
        }
    }
}

/**
 * 用水浒英雄模拟单链表的使用
 */
class HeroNode {
    public int num;
    public String name;
    public String nickName;
    public HeroNode next;
    //构造器
    public HeroNode(int num, String name, String nickName){
        this.num = num;
        this.name = name;
        this.nickName = nickName;
    }

    /**
     * 重写toString方法
     * @return
     */
    @Override
    public String toString() {
        return "{HeroNode: [id: " + this.num + "], [name: " + this.name + "], [nickname: " + this.nickName + "]}";
    }
}